# -*- coding: utf-8 -*-

"""剑指 Offer II 056. 二叉搜索树中两个节点之和
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

示例 1：
输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12

示例 2：
输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点

提示：
二叉树的节点个数的范围是  [1, 10^4].
-10^4 <= Node.val <= 10^4
root 为二叉搜索树
-10^5 <= k <= 10^5"""


# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    """构造一个中序遍历的生成器迭代器，单调迭代一个值，由于本身就是二叉搜索树，同时就用二叉搜索来找也很快
    题解中说用中序遍历，形成单调数组，再利用双指针。但是斯认为一开始就将所有节点构造成一个单调数组，没有充分发挥二叉搜索树的作用"""
    def findTarget(self, root: TreeNode, k: int) -> bool:
        iterator = self.__iterate(root)
        while True:
            try:
                node = next(iterator)
                targert = k-node.val
                nodet = self.__search(root, targert)
                if nodet and nodet is not node:
                    return True
            except StopIteration:
                return False


    def __iterate(self, node):
        if node.left:
            yield from self.__iterate(node.left)
        yield node
        if node.right:
            yield from self.__iterate(node.right)

    def __search(self, node, targert):
        nodet = None
        while True:
            if targert == node.val:
                nodet= node
                break
            elif targert < node.val:
                if node.left:
                    node = node.left
                else:
                    break
            elif targert > node.val:
                if node.right:
                    node = node.right
                else:
                    break
        return nodet


